package com.leetcode.two_pointers.sliding_window;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author Dennis Li
 * @date 2020/9/16 16:58
 */
public class LengthOfLongestSubstring_3 {

    public int lengthOfLongestSubstring(String s) {
        // 记录当前字符的坐标
        Map<Character, Integer> map = new HashMap<>();
        char[] array = s.toCharArray();
        int left = 0, max = 0;
        for (int right = 0; right < array.length; right++) {
            char ch = array[right];
            // 如果存在该字符，那么将左指针指向这个位置的后一位
            if (map.containsKey(ch)) {
                // left 不会向左移动
                left = Math.max(map.get(ch) + 1, left);
            }
            map.put(ch, right);
            max = Math.max(max, right - left + 1);
        }
        return max;
    }

    static class Solution {
        public int lengthOfLongestSubstring(String s) {
            Set<Character> window = new HashSet<>();
            int max = 0, left = 0, right = 0;
            while (right < s.length()) {
                char rc = s.charAt(right);
                right++;
                if (!window.contains(rc)) {
                    window.add(rc);
                } else {
                    while (left < right) {
                        char lc = s.charAt(left);
                        left++;
                        if (lc == rc) break;
                        else window.remove(lc);
                    }
                }
                max = Math.max(max, window.size());
            }
            return max;
        }
    }

}
